/**
 * File name: KMedoids.java Author: Willard Wang Create date: Aug 24, 2013
 */
package edu.sjtu.se.prophet.cluster;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

import org.apache.log4j.Logger;

import edu.sjtu.se.prophet.cluster.SimpleFastMedoids.Pair;

/**
 * @author deathspeeder
 * 
 */
public class KMedoids extends BaseMedoids {

    private static Logger logger = Logger.getLogger(KMedoids.class);

    private boolean hasChangeInMedoids = true;


    // /*
    // * (non-Javadoc)
    // *
    // * @see edu.sjtu.se.prophet.cluster.Clusterer#cluster(java.util.Collection,
    // * edu.sjtu.se.prophet.cluster.DistanceMeter, int)
    // */
    // @Override
    // public Collection<Cluster> cluster(Collection<Point> points,
    // DistanceMeter meter, int numberOfClusters)
    // throws InvalidClusterNumberException {
    //
    // if (numberOfClusters <= 0 || numberOfClusters > points.size())
    // throw new InvalidClusterNumberException("numberOfClusters="
    // + numberOfClusters + ", number of points=" + points.size());
    //
    // this.points = points;
    // this.meter = meter;
    // this.numberOfClusters = numberOfClusters;
    //
    // logger.info("Number of points: " + points.size()
    // + ", number of clusters: " + numberOfClusters);
    //
    // init();
    //
    // int iteration = 0;
    //
    // while (hasChangeInMedoids) {
    // iteration++;
    // logger.info("Cluster iteration " + iteration);
    //
    // hasChangeInMedoids = false;
    //
    // logger.info("associateDataPoints");
    // associateDataPoints();
    //
    // logger.info("findLowestCostConfifuration");
    // findLowestCostConfifuration();
    //
    // }
    //
    // return clusters;
    // }

    /**
     * 
     */
    private void findLowestCostConfifuration() {
        // for (Cluster c : clusters) {
        // System.out.print("Cluster:");
        // for (Point p : c.getPoints())
        // System.out.print(" " + p);
        // logger.info();
        // }
        // for (Point p : medoids) {
        // logger.info(p);
        // }

        int costBefore = getCost();
        int lowerCost = costBefore;
        logger.info("Cost before: " + costBefore);
        Point swapMedoid = null;
        Point swapDataPoint = null;

        Set<Point> medoidsCopy = new HashSet<Point>(medoids);

        int debugIndex1 = 0;
        // int debugIndex2 = 0;
        for (Point medoid : medoidsCopy) {
            logger.debug("Medoid index " + debugIndex1);
            // debugIndex2 = 0;
            for (Point point : points) {
                if (!medoids.contains(point)) {
                    // swap(medoid, point);
                    int newCost = getSwapCost(medoid, point, costBefore);
                    // logger.info("Try cost " + medoid + " " + point + ": " +
                    // newCost);
                    if (newCost < lowerCost) {
                        logger.info("New lower cost: " + newCost + " medoid: "
                                + medoid + ", data point: " + point);
                        lowerCost = newCost;
                        swapMedoid = medoid;
                        swapDataPoint = point;
                        hasChangeInMedoids = true;
                    }
                    // swap(point, medoid);
                }
            }
            debugIndex1++;
        }

        if (hasChangeInMedoids) {
            swap(swapMedoid, swapDataPoint);
        }

    }


    private int getSwapCost(Point medoid, Point point, int cost) {
        MedoidCluster pointCluster = (MedoidCluster) point.getCluster();
        int before = 0;
        int after = 0;
        // the medoid and point are in the same cluster
        if (pointCluster.medoid == medoid) {
            for (Point p : pointCluster.getPoints()) {
                before += meter.distance(p, medoid);
                after += meter.distance(p, point);
            }
        } else {
            for (Point p : medoid.getCluster().getPoints()) {
                before += meter.distance(p, medoid);
                if (p != medoid)
                    after += meter.distance(p, point);
            }
            before += meter.distance(point, pointCluster.medoid);
            after += meter.distance(medoid, pointCluster.medoid);
        }
        return cost - before + after;
    }


    // private double getSwapCost(Point medoid, Point point, double cost) {
    // double medoidCost = getCost(medoid);
    // logger.info(medoidCost);
    // MedoidCluster pointCluster = (MedoidCluster) point.getCluster();
    // double pointCost = meter.distance(point, pointCluster.medoid);
    // logger.info(pointCluster.medoid);
    // logger.info(pointCost);
    //
    // double newMedoidCost = 0;
    // for (Point p : medoid.getCluster().getPoints()) {
    // if (p != medoid)
    // newMedoidCost += meter.distance(p, point);
    // }
    // if (pointCluster.medoid == medoid)
    // newMedoidCost += meter.distance(medoid, point);
    // logger.info(newMedoidCost);
    // double newPointCost = meter.distance(medoid, pointCluster.medoid);
    // logger.info(newPointCost);
    // return cost - medoidCost - pointCost + newMedoidCost + newPointCost;
    // }

    /**
     * @param point
     * @param medoid
     */
    private void swap(Point medoid, Point point) {
        // logger.info("swap " + medoid + ", " + point);
        MedoidCluster medoidCluster = (MedoidCluster) medoid.getCluster();
        MedoidCluster dataCluster = (MedoidCluster) point.getCluster();
        medoid.moveTo(dataCluster);
        point.moveTo(medoidCluster);
        medoidCluster.setMedoid(point);

        medoids.remove(medoid);
        medoids.add(point);

        // logger.info("medoid " + medoidCluster.getMedoid() + ", " +
        // dataCluster.getMedoid());
    }


    private void init() {

        // random unmberOfClusters medoids
        Point[] pointsArray = points.toArray(new Point[0]);
        medoids = new HashSet<Point>();

         Random random = new Random();
         while (medoids.size() < numberOfClusters) {
         Point randomPoint = pointsArray[random.nextInt(numberOfClusters)];
         if (!medoids.contains(randomPoint))
         medoids.add(randomPoint);
         }

//        for (int i = 0; i < numberOfClusters; i++) {
//            int maxDistances = Integer.MIN_VALUE;
//            Point selected = null;
//            for (Point point : points) {
//                if (!medoids.contains(point)) {
//                    int distance = 0;
//                    for (Point medoid : medoids) {
//                        distance += meter.distance(point, medoid);
//                    }
//                    if (distance > maxDistances) {
//                        maxDistances = distance;
//                        selected = point;
//                    }
//                }
//            }
//            if (selected != null) {
//                medoids.add(selected);
//            }
//        }

        // /**
        // * Calculate distance ratio defined by Fast K-medoids:
        // * for point j,
        // * v_j=sum_{i=1}^n {d_ij}/{sum_{l=1}^n d_il}
        // *
        // * Select the first k smallest as initial medoids
        // */
        // List<Pair> vectors = new ArrayList<Pair>();
        // for (Point j : points) {
        // double vector = 0;
        // for (Point i : points) {
        // int divident = 0;
        // for (Point l : points) {
        // divident += meter.distance(i, l);
        // }
        // if (divident == 0) {
        // vector = Double.MAX_VALUE;
        // break;
        // } else
        // vector += ((double) meter.distance(i, j) / divident);
        // }
        // vectors.add(new Pair(vector, j));
        // }
        //
        // Collections.sort(vectors);
        //
        // medoids = new HashSet<Point>();
        // for (int i = 0; i < numberOfClusters; i++) {
        // medoids.add(vectors.get(i).point);
        // //System.out.println(vectors.get(i).point);
        // }

        clusters = new ArrayList<Cluster>();
        for (Point medoid : medoids) {
            clusters.add(new MedoidCluster(medoid));
        }

    }


    @Override
    protected Collection<Cluster> cluster() {

        init();

        int iteration = 0;

        while (hasChangeInMedoids) {
            iteration++;
            logger.info("Cluster iteration " + iteration);

            hasChangeInMedoids = false;

            logger.info("associateDataPoints");
            associateDataPoints();

            logger.info("findLowestCostConfifuration");
            findLowestCostConfifuration();

        }

        return clusters;
    }

}
